/**
 * 剑指 Offer 04. 二维数组中的查找
 * https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
 */

// /**
//  * @param {number} target
//  * @param {number[][]} matrix
//  * @param {number} begin
//  * @param {number} end
//  * @param {boolean} vertical
//  * @param {number} base
//  * @return {number}
//  */
// function findIndex(target, matrix, begin, end, vertical, base) {
//   let left = begin;
//   let right = end;
//   while (left <= right) {
//     const middle = Math.floor((left + right) / 2);
//     const middleVal = vertical ? matrix[middle][base] : matrix[base][middle];
//     if (middleVal === target) {
//       return middle;
//     }
//     if (middleVal < target) {
//       if (
//         middle >= end
//         || (vertical ? matrix[middle + 1][base] : matrix[base][middle + 1]) > target
//       ) {
//         return middle;
//       }
//       left = middle + 1;
//     } else {
//       right = middle - 1;
//     }
//   }
//   return -1;
// }
//
// /**
//  * @param {number[][]} matrix
//  * @param {number} target
//  * @return {boolean}
//  */
// function findNumberIn2DArray(matrix, target) {
//   let verticalEnd = matrix.length - 1;
//   let horizontalBegin = 0;
//   while (verticalEnd >= 0 && horizontalBegin < matrix[0].length) {
//     const verticalIndex = findIndex(target, matrix, 0, verticalEnd, true, horizontalBegin);
//     if (verticalIndex >= 0) {
//       if (matrix[verticalIndex][horizontalBegin] === target) {
//         return true;
//       }
//       verticalEnd = verticalIndex;
//     } else {
//       return false;
//     }
//     const horizontalIndex = findIndex(target, matrix, horizontalBegin, matrix[0].length - 1, false, verticalEnd);
//     if (horizontalIndex >= 0) {
//       if (matrix[verticalEnd][horizontalIndex] === target) {
//         return true;
//       }
//       horizontalBegin = horizontalIndex + 1;
//     } else {
//       return false;
//     }
//   }
//   return false;
// }

/**
 * 从右上角开始线性查找
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
function findNumberIn2DArray(matrix, target) {
  if (!matrix.length) {
    return false;
  }
  let i = 0;
  let j = matrix[0].length;
  while (i < matrix.length && j >= 0) {
    if (target === matrix[i][j]) {
      return true;
    }
    if (target > matrix[i][j]) {
      i += 1;
    } else {
      j -= 1;
    }
  }
  return false;
}

console.log(findNumberIn2DArray(
  [
    [1, 4, 7, 11, 15],
    [2, 5, 8, 12, 19],
    [3, 6, 9, 16, 22],
    [10, 13, 14, 17, 24],
    [18, 21, 23, 26, 30],
  ],
  5,
) === true);
console.log(findNumberIn2DArray(
  [
    [1, 4, 7, 11, 15],
    [2, 5, 8, 12, 19],
    [3, 6, 9, 16, 22],
    [10, 13, 14, 17, 24],
    [18, 21, 23, 26, 30],
  ],
  20,
) === false);
